package site.wanjiahao;

public class LIS {

    public static void main(String[] args) {
        int[] nums = {10, 2, 2, 5, 1, 7, 101, 18};

        System.out.println(lis(nums));
    }

    // 二分法，寻找的过程中，实际是确定已经排好序的元素的位置
    static int lis(int[] nums) {
        // 维护一个数组，记录牌顶元素
        int[] top = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int begin = 0;
            int end = len;
            while (begin < end) {
                int mid = (begin + end) >> 1;
                if (num > top[mid]) {
                    begin = mid + 1;
                } else {
                    end = mid;
                }
            }

            top[begin] = num;
            if (begin == len) {
                len++;
            }
        }
        // 当前牌顶元素的多少，就是最大上升子序列的长度
        return len;
    }

    // 扑克牌，实现最长上升序列
    static int lis2(int[] nums) {
        // 维护一个数组，记录牌顶元素
        int[] top = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int index = 0;
            while (index < len) {
                if (num <= top[index]) {
                    // 看下当前num是否小于牌顶元素
                    top[index] = num;
                    break;
                }
                index++;
            }
            if (index == len) {
                top[len++] = num;
            }
        }
        // 当前牌顶元素的多少，就是最大上升子序列的长度
        return len;
    }


    // 最长上升子序列
    static int lis1(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int len = nums.length;
        int[] dp = new int[len + 1];
        int max = 1;
        dp[0] = max;
        for (int i = 1; i < len; i++) {
            // 设置默认长度值
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] <= nums[j]) continue;
                // 确定子序列中最大的那个
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

}
